package _stack_queue;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.PriorityBlockingQueue;

/*

https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
https://leetcode.cn/problems/top-k-frequent-elements/description/

    347. 前 K 个高频元素

    给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

    示例 1:

    输入: nums = [1,1,1,2,2,3], k = 2
    输出: [1,2]
    示例 2:

    输入: nums = [1], k = 1
    输出: [1]



 */
public class leetcode_347 {
    @Test
    public void test() {
        int[] actual = topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2);
        int[] expect = new int[]{2, 1};
        Assert.assertEquals(Arrays.toString(expect), Arrays.toString(actual));
    }

    /***
     1 loop the array, count the num of value
     2 item -> class pair
     3 mao -> PriorityBlockingQueue (smll -> big) - paire
     offer item
     if(queue >k){
     poll top
     }
     4 PriorityBlockingQueue -> array

     T - NLogK
     S - N
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int n : nums) {
            if (map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            } else {
                map.put(n, 1);
            }
        }
        PriorityBlockingQueue<Pair> q = new PriorityBlockingQueue<Pair>();
        // TODO : entrySet 易错
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            q.offer(new Pair(entry.getKey(), entry.getValue()));
            if (q.size() > k) {
                q.poll();
            }
        }

        int size = q.size();
        int[] result = new int[size];
        for (int i = 0; i <= size - 1; i++) {
            result[i] = q.poll().value;
        }
        return result;
    }

    // TODO : Comparable 易错
    static class Pair implements Comparable<Pair> {
        public int value;
        public int count;

        Pair(int value, int count) {
            this.value = value;
            this.count = count;
        }

        // TODO : compareTo 易错
        public int compareTo(Pair another) {
            // TODO : compare 易错
            return Integer.compare(count, another.count);
        }
    }

}
